/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ${USER}
 * Date: ${YEAR}-${MONTH}-${DAY}
 * Time: ${TIME}
 */
import javax.swing.tree.TreeNode;
import java.util.HashMap;
import java.util.Scanner;


class Solution10{
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int n  = mat.length;
        int m = mat[0].length;
        int[][] ans = new int[n][m];
        int[][] dp = new int[n + 1][m + 1];
        for(int i = 1; i < dp.length; i++){
            for(int j = 1; j < dp[0].length; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        for(int i = 0; i < ans.length; i++){
            for(int j  = 0; j < ans[0].length; j++){
                int x1 = Math.max(0, i - k) + 1;
                int y1 = Math.max(0, j - k) + 1;
                int x2 = Math.min(n - 1, i + k) + 1;
                int y2 = Math.min(m - 1, j + k) + 1;
                ans[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        }
        return ans;
    }
}
class Solution9{
    public int findMaxLength(int[] nums) {
        int ret = 0;
        HashMap<Integer, Integer> hash = new HashMap<>(); //存前缀和，下标
        hash.put(0, -1);//整个数组为0, 那么下标是-1 ，整个数组长度 - (-1)
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += (nums[i] == 0 ? -1 : 1); //把0变成-1， 问题转换为找和为0的最长子数组
            if(hash.containsKey(sum)){  //如果sum - 0 存在重复，那么计算长度即可，不用更新后面的下标(找最短， 用长度-最短 = 最长)
                ret = Math.max(ret, i - hash.get(sum));
            }else{
                hash.put(sum, i); //存入sum前缀和
            }
        }
        return ret;
    }
}
class Solution8 {
    public int findMaxLength(int[] nums) {
        int ret = 0;
        HashMap<Integer, Integer> hash = new HashMap<>(); //存前缀和，下标
        hash.put(0, -1);//整个数组为0, 那么下标是-1 ，整个数组长度 - (-1)
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += (nums[i] == 0 ? -1 : 1); //把0变成-1， 问题转换为找和为0的最长子数组
            if(hash.containsKey(sum)){  //如果sum - 0 存在重复，那么计算长度即可，不用更新后面的下标(找最短， 用长度-最短 = 最长)
                ret = Math.max(ret, i - hash.get(sum));
            }else{
                hash.put(sum, i); //存入sum前缀和
            }
        }
        return ret;
    }
}
class Solution7{
    public int subarraysDivByK(int[] nums, int k) {
        int sum = 0;
        int ret = 0;
        HashMap<Integer, Integer> hash = new HashMap<>();
        hash.put(0, 1); //整个数组能被K整除, 在0, -1 去找？不合法，提前设置
        for(int i = 0; i < nums.length; i++){
            sum += nums[i]; //计算当前元素
            ret += hash.getOrDefault((sum % k + k) % k, 0); //获取计算i之前的[0. i - 1]区间sum % k 个数, 想知道[x, i]有多少子数组能被k整除，求[0, x]之间有多少能被k整除
            hash.put((sum % k + k) % k , hash.getOrDefault((sum % k + k) % k, 0) + 1); //在计算i这个元素之前丢进哈希表才是[0, i - 1]之前的查找区间
        }
        return ret;
    }
}
class Solution6{
    public String minWindow(String s, String t) {
        int[] hash1 = new int[128];
        int[] hash2 = new int[128];
        int kinds = 0;
        for(int i = 0; i < t.length(); i++){
            char in = t.charAt(i);
            if(hash1[in]++ == 0){
                kinds++;    //统计多少种字符
            }
        }
        int begin = -1;
        int minLen = Integer.MAX_VALUE;
        for(int left = 0, right = 0, cnt = 0; right < s.length(); right++){
            char in = s.charAt(right);
            if(++hash2[in] == hash1[in]){
                cnt++;
            }
            while(cnt == kinds){
                if(right - left + 1 < minLen){
                    begin = left;
                    minLen = right - left + 1;
                }
                char out = s.charAt(left++);
                if(hash2[out]-- == hash1[out]){
                    cnt--;
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(begin, begin + minLen);
    }
}
class Solutio05n {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ret = new int[n];
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = g[n - 1] = 1;  //后面求f[0]和g[n - 1]的时候让g[i] 或者 是 f[i] 不是乘0
        for(int i = 1; i < n; i++){
            f[i] = f[i - 1] * nums[i - 1];
        }
        for(int i = n - 2; i >= 0; i--){
            g[i] = g[i + 1] * nums[i + 1];
        }
        for(int i = 0; i < n; i++){
            ret[i] = f[i] * g[i];
        }
        return ret;
    }
}
class Solution4 {
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        for(int i = 1; i < n; i++){
            f[i] = f[i - 1] + nums[i - 1];
        }
        for(int i =  n - 2; i >= 0; i--){
            g[i] = g[i + 1] + nums[i + 1];
        }
        for(int i = 0; i < n; i++){
            if(f[i] == g[i]){
                return i;
            }
        }
        return -1;
    }
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
class Main2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n + 1];
        for(int i = 1; i < arr.length; i++){
            arr[i] = in.nextInt();
        }
        long[] dp = new long[n + 1];
        for(int i = 1; i < dp.length; i++){
            dp[i] = dp[i - 1] + arr[i];
        }
        while(m != 0){
            int l = in.nextInt();
            int r = in.nextInt();
            System.out.println(dp[r] - dp[l - 1]);
            m--;
        }
    }
}
class Solution3{
    public int takeAttendance(int[] records) {
        int left = 0;
        int right = records.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(records[mid] == mid){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        if(records[left] == left){
            return left + 1;
        }else{
            return left;
        }
    }
}
class Solution2 {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] >= nums[0]){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        if(nums[0] < nums[nums.length - 1]) return nums[0];
        else return nums[left];
    }
}
class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[mid + 1]){  //right是mid是因为mid > mid + 1的时候mid是峰值
                right = mid;
            }else{
                left = mid + 1; //left = mid + 1是因为mid <= mid + 1的时候mid + 1是峰值
            }
        }
        return left;
    }
}
public class Main {
    public static void main(String[] args) {
        System.out.println("hello world");
    }
}